A. Maximum GCD
题目大意:给定一个正整数,找到两个数满足,且gcd(a,b)a,b$具体是多少,只需要gcd的值).
数据范围:
枚举若干个数可以发现,如果是奇数,则应该是前面的和的gcd作为答案,因为奇数至少也要除,必然比偶数的小.偶数同理.最终结果就是
B. GCD Compression
题目大意:有一个长度为的序列,现在想把他压缩到长度的序列.按如下操作方式压缩:首先任意丢掉里的两个元素,之后任取两个中的元素,删掉他们俩,再把他们俩的和加入.注意第一次是直接丢掉的.要求整个序列的gcd大于,即.
数据范围:
显然正面直接构造相当困难,选择太多了.注意到题目的数据非常小,,由于这个条件,我们可以得到一个重要条件:即整个序列是有一个比大的公共因数的,并且由于所有的数都比小,所以可以直接枚举这个因数具体是谁,按余数对进行分类.如果有一组的个数是奇数,那么就要把这一组里的一个数删掉(对应题目开始时的操作),因为是两两相组,所以奇数必然会剩下一个.最多可以删次.
最后看是不是满足条件的就可以了.不过还需要注意:第一步是不能不做的,如果不符合条件的恰好只有一个,那么删去就行了,如果一个都没有,你也不能不删,随便挑一个删去就可以了.对应到代码里就是到最后发现,过多了,需要多删一组.
其次,容易想到这个公共的因子肯定得是一个质数,如果是合数其实是没意义的,进一步可以降低复杂度.从小到大依次枚举每个质数,再进行分类,就可以做掉这道题了.(是不是直接枚举因数就可以过掉我也没试过,可以自己尝试一下)
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1005;
int primes[N],st[N],cnt;
vector<int> edges[N];
void init()
{
for(int i = 2;i < N;++i)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0;i * primes[j] < N;++j)
{
st[primes[j] * i] = 1;
if(i % primes[j] == 0) break;
}
}
}
int main()
{
init();
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);n *= 2;
vector<int> a(n + 17,0);
for(int i = 0;i < n;++i) scanf("%d",&a[i]);
if(n == 4)
{
printf("3 4\n");
continue;
}
for(int i = 0;i < cnt;++i)
{
int ok = 3;
int div = primes[i];
for(int j = 0;j < div;++j) edges[j].clear();
for(int j = 0;j < n;++j)
edges[a[j] % div].push_back(j);
vector<pii> res;
for(int j = 0;j < div;++j)
{
if(edges[j].size() % 2)
{
if(ok)
{
--ok;
edges[j].pop_back();
}
else break;
}
for(int k = 0;k < edges[j].size();k += 2)
res.push_back({edges[j][k] + 1,edges[j][k + 1] + 1});
}
if(ok)
{
for(auto& v : res)
{
if(ok > 2)
{
--ok;
continue;
}
printf("%d %d\n",v.first,v.second);
}
break;
}
}
}
return 0;
}
C. Number Game
题目大意:两个人在玩一个游戏,一开始有一个正整数,每一次可以除掉的一个奇因子.或者减一.当的时候上述操作都不能进行.先不能采取任何行动的玩家输,问是否是先手必胜的.
注意:奇因子是包含自己的.
数据范围:
显然,除了之外的所有奇数都是先手必胜的.现在的问题就是偶数是怎样判明的:观察样例可以发现肯定不是直接跟偶数相关的,可能跟其内有几个偶数几个奇数有关.考虑把偶数变成一个更数学化的形式:对于一个偶数,他可以表示成若干个奇质数乘积和一个的幂的乘积形式,即其中全是奇质数,不包含.由于说奇数是必胜状态,这个问题的转化方向肯定是和的幂具体是多少有关,一个一个来考虑一下试试:
首先,如果,即原来的数里只有一个存在的话:
①他就是,没有一个奇因子,显然是必胜的.
②至少有一个奇因子存在,这个时候可以把所有的奇因子全部除掉,就剩下一个,而显然是一个必胜状态,这样就必败了.所以这个时候还要考虑的是有几个,因为如果只有一个的话,无论是减一也好还是除掉奇因子也好,必然会给这个数或者是一个奇数(因为偶数减一必然是奇数)让给对手,就必败了.如果有多个的话,那么我只要留下一个这个状态给对手,对手显然就是一个必败状态,而我是一个必胜状态了.因为之前说了如果手上只有一个奇因子,一定会把必胜状态给对手,导致必败.
综上,如果没有奇因子,则必胜,如果只有一个,则必败,如果有一个以上,则必胜.
当然,对于这种情况,如果没有奇因子的时候就是单纯的,在去掉这个之后如果还是一个质数的话,则对应只有一个奇因子,必败.反之是一个合数,表示有多个奇因子,必胜.可能要稍微好写一点.
其次,如果有多个,即的话,情况又会有变:
①假设手上就是一个,没有奇因子,只能执行操作给对手一个奇数,导致必败.
②如果手上只有一个奇因子的话,肯定不会去减一,减一相当于直接送分.去掉一个奇因子的话,剩下的一个到对手手上,只能是操作,得到一个奇数再还回来,因此必胜.
③如果有多个奇因子同②.
综上,如果没有奇因子,必败,如果有则必胜.
对上述两种情况分别讨论即可.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int primes[N],st[N],cnt;
bool isprime(int x)
{
for(int i = 2;i <= x / i;++i)
if(x % i == 0)
return 0;
return 1;
}
void lose()
{
puts("FastestFinger");
}
void win()
{
puts("Ashishgup");
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
// cout << (n / 2) << endl;
if(n == 1) lose();
else if(n == 2) win();
else if(n % 2) win();
else
{
// cout << contain << endl;
if(n % 4 == 0)
{
while(n % 2 == 0) n /= 2;
if(n == 1) lose();
else win();
}
else
{
n /= 2;
if(isprime(n)) lose();
else win();
}
}
}
return 0;
}
D. Odd-Even Subsequence
题目大意:有一个长度为的序列,找到的一个子序列,他的长度为,使这个子序列的偶数位置上的最大值和奇数位置上的最大值两者的最小值最小.输出这个最小值即可,不需要输出具体方案.
定义子序列是删去序列里若干个元素,但不改变剩余元素的相对位置得到的序列.
注意,是里的奇数位置和偶数位置,不是这个元素之前在里的位置.
数据范围:
这题乍看上去也是挺牛逼的,没啥想法.不过可以注意到,最终的答案表达式是两边最大值的最小值,既然如此,突破口可能就是在这里,因为这个最小值意味着我可以让一边很大但是一边很小,反正答案是取得最小值,我另一边取的再大都没问题.
如果把这些条件都去掉的话,可以发现这就是一个二分答案的题:首先确定一个答案表示整个序列里的最大值最多是多少,判断就是看整个序列最少有几个,长度如果达到就说明当前这个答案是可以构造出来的.带到本题里可以发现正确性是比较接近的,但是由于有些条件暂时没联系起来可能有问题,顺着往下想:
确定一个答案之后,在这道题里,检测一个答案是否是可以构造的,应该要有两种:一次是奇数上的,一次是偶数上的.为什么要这样做,之前也解释过了,因为答案是两者中的最小值,所以另一边无论怎样大或者小都是无所谓的,我只要管一边就行了.
做两个的目的就是把两种情况都找出来,只要有一个就说明这个答案是可行的,答案还可以继续缩小.具体实现的方式就是遍历,对于找奇数位置的来说,偶数位置直接加进去(长度),奇数位置看是不是小于当前答案的,如果是就长度增加.直接套一个二分框架这个题就做出来了.
注意在实现的时候,如果说当前的位置是需要判断大小来看是否能填入序列的,那么只有在填入了一个数的情况下状态才能改变,因为如果你没填的话这个状态变了就不对了,因为位置是在里的位置而不是里的位置,这一点需要注意一下.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
const int N = 2e5+7;
int a[N];
bool check(int x,bool islf)
{
int fres = 0;
for(int i = 1;i <= n;++i)
{
if(islf)
{
if(a[i] <= x)
{
++fres;
islf = 0;
}
}
else
{
++fres;
islf = 1;
}
}
return fres >= k;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
int l = 0,r = 1e9,res;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid,0) || check(mid,1)) r = mid;
else l = mid + 1;
}
printf("%d",l);
return 0;
}
E. Binary Subsequence Rotation
题目大意:给两个二进制串和,规定一种操作:每次操作中你可以任取几个位置,把这几个位置里的元素挑出来,往右循环旋转一次(即往右移动一格,最后一个变成开头的),再把新的几个元素按顺序填回去.问最少要几次这样的操作使变成.只输出次数,不输出具体方案,如果问题无解则输出.
数据范围:
显然当两个串的字符数量不对等的时候问题无解.
其次由于整个序列里旋转的位置是可以随便选的,所以如果已经相同的一对位置是毫无意义的,可以直接删掉,我们只用考虑上下不同的对.很显然这样的对只有两种,要么是,要么是.其次考虑至少要多少次.可以发现如果是一段的串,只要循环旋转一次就够了,也就是这样的交替序列只需要操作一次.这里用两个计数变量,一个表示以为结尾的有几个,另一个表示以结尾的串有多少个.遍历所有不同对,如果是形式的,就看有没有的串在前面,如果有,则并,如果没有一个的串在前面的话,就说明现在只能多开一个序列了直接即可,另外一种情况对称处理即可.显然答案就是.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
char a[N],b[N];
int s[N];
int n,m;
int main()
{
scanf("%d",&n);
scanf("%s",a + 1);getchar();
scanf("%s",b + 1);
int x0 = 0,x1 = 0;
for(int i = 1;i <= n;++i)
{
if(a[i] == b[i]) continue;
s[++m] = a[i] - '0';
if(a[i] == '1') ++x1;
else ++x0;
}
if(x1 != x0)
{
puts("-1");
return 0;
}
if(!m) puts("0");
else
{
int res = 0;
int f1 = 0,f0 = 0;
for(int i = 1;i <= m;++i)
{
if(s[i] == 1)
{
if(f0) --f0,++f1;
else ++f1;
}
else
{
if(f1) --f1,++f0;
else ++f0;
}
}
printf("%d",f0 + f1);
}
return 0;
}